<?php
/*
 * This file is part of MVD_GUI.
 *
 *  MVD_GUI is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  MVD_GUI is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with MVD_GUI.  If not, see <http://www.gnu.org/licenses/>.
 *  Copyright 2010 Desmond Schmidt
 */
// no direct access
 
defined( '_JEXEC' ) or die( 'Restricted access' );
 
jimport( 'joomla.application.component.view');
define( "MIN_SNAKE", 5 );
/**
 * Single version view class for the MVD Component
 */
 
class MvdViewMvdsingle extends JView
{
	public $html;
	public $vt;
	public $version;
	public $name;
	/** hash: html->xml offsets*/
	public $offsets;
	/**
	 * The text for this view is changing or is being set for 
	 * the first time. We must convert the TEI-XML into HTML.
	 * @param xml the xml from the version
	 * @param version the version id
	 * @param vt the version table for this mvd
 	 */
	function setText( $xml, $versionId, $name, $vt )
	{
		$this->vt = $vt;
		$this->version = $versionId;
		$this->name = $name;
		$xp = new XsltProcessor();
		$xsl = new DomDocument;
		$xsl->load( JPATH_BASE.DS."components".DS."com_mvd"
			.DS."xsl".DS."formats.xsl" );
		$xp->importStylesheet( $xsl );
		$xmlDoc = new DomDocument;
		$xmlDoc->loadXML( $xml );
		$this->html = $xp->transformToXML($xmlDoc);
		$this->html = trim( $this->html );
      	if ( !$this->html )
			echo "<p>Transform failed</p>";
		else
		{
			$this->offsets = array();
			//$starttime = microtime(true);
			$this->noteXMLOffsets( $xml, $this->html, 0, 0, 
				strlen($xml), strlen($this->html) );
			/*$off = "";
			foreach ( $this->offsets as $key=>$value )
				$off .= $key.'->'.$value.',';
			error_log("offsets=$off<br>");
			$endtime = microtime(true)-$starttime;
			error_log("Time taken for LCS: $endtime");*/
		}
	}
	/**
	 * Use a simple recursive heuristic to compute the LCS. From the LCS 
	 * we can easily compute the table of offsets for conversion of offsets 
	 * in HTML to offsets in the XML. Not 100% reliable but very fast. 
	 * (We can't afford an O(MN) or even O(ND) algorithm.)
	 * The idea is divide and conquer. We identify the longest invariant 
	 * string by just sampling the edit graph and extending whenever we find 
	 * snakes. We take that as part of the LCS. Then we recurse into the left 
	 * and right hand portions of the graph, so building up an approximate LCS.
	 * Runtime for one Cerami story is about 0.2 seconds, and roughly linear.
	 * @param xml reference to the xml text being pasted in
	 * @param html the html transformed out of the xml
	 * @param startx the offset within xml to start from
	 * @param starty the offset within html to start from
	 * @param xlen the length of the xml text being considered
	 * @param ylen the length of the html text being considered
	 */
	function noteXMLOffsets( &$xml, &$html, $startx, 
		$starty, $xlen, $ylen )
	{
		$maxlen = 0;
		$bestx = 0;
		$besty = 0;
		$x = $startx;
		$y = $starty;
		// N, M one beyond end
		$N = $startx+$xlen;
		$M = $starty+$ylen;
		// sample three stripes through
		$y1 = $starty + round($ylen/4);
		$y2 = $starty + round($ylen/2);
		$y3 = $starty + round(3*$ylen/4);
		while ( $x<$N )
		{
			if ( $xml[$x]==$html[$y1] )
				$this->findSnakes( $x, $y1, $xml, $html, $maxlen, 
					$bestx, $besty );
			if ( $xml[$x]==$html[$y2] )
				$this->findSnakes( $x, $y2, $xml, $html, $maxlen, 
					$bestx, $besty );
			if ( $xml[$x]==$html[$y3] )
				$this->findSnakes( $x, $y3, $xml, $html, $maxlen, 
					$bestx, $besty );
			$x++;
		}
		// see what the scan turned up
		if ( $maxlen > MIN_SNAKE )
		{
			$this->offsets[$besty] = $bestx;
			// now recurse
			if ( ($bestx-$startx > MIN_SNAKE)
				&& ($besty-$starty > MIN_SNAKE) )
			{
				$this->noteXMLOffsets( $xml, $html, $startx, 
					$starty, $bestx-$startx, $besty-$starty );
			}
			if ( $N-($bestx+$maxlen) > MIN_SNAKE 
				&& $M-($besty+$maxlen) > MIN_SNAKE )
			{
				$newStartX = $bestx+$maxlen;
				$newStartY = $besty+$maxlen;
				$this->noteXMLOffsets( $xml, $html, $newStartX, 
					$newStartY, $N-$newStartX, $M-$newStartY );
			}
		}
		// else nothing significant, forget it
	}
	/**
 	 * We have a match at x,y. See if we can extend it and so uncover 
	 * the longest invariant section. Update maxlen, bestx and besty.
	 * @param x the x-coordinate into xml
	 * @param y the y-coordinate into html
	 * @param xml reference ot the xml text before transformation
	 * @param html reference to the html after transformation
	 * @param maxlen reference to length of the longest snake found so 
	 * far
	 * @param bestx reference to the x-coordinate of the maxlen snake
	 * @param besty reference to the y-coordinate of the maxlen snake
	 */
	function findSnakes( $x, $y, &$xml, &$html, &$maxlen, 
		&$bestx, &$besty )
	{
		$x2 = $x;
		$y2 = $y;
		$len = 0;
		// extend down
		while ( $x2<$N && $y2<$M 
			&& $xml[$x2]==$html[$y2] )
		{
			$len++;
			$x2++;
			$y2++;
		}
		// extend up
		$posx = $x;
		$posy = $y;
		$x2 = $x-1;
		$y2 = $y-1;				
		while ( $x2>=$startx && $y2>=$starty 
			&& $xml[$x2]==$html[$y2] )
		{
			$len++;
			// save last *matching* position 
			$posx = $x2;
			$posy = $y2;
			$x2--;
			$y2--;
		}
		if ( $len > $maxlen && $len > MIN_SNAKE )
		{
			$maxlen = $len;
			$bestx = $posx;
			$besty = $posy;
		}
	}
	/**
	 * Just call the superclass
	 */
	function display($tpl = null)
    {
        parent::display($tpl);
    }
}
